import java.util.Date;

/**
 * @author AlfredCai
 */
public class Sort {
    /**
     * 选择排序
     * 向后找最小的一个数放在当前位置
     */
    public static void Selection(int[] array) {
        long start = System.currentTimeMillis();
        System.out.println("选择排序");
        int N = array.length;
        for (int i = 0; i < N; i++) {
            int min = array[i];
            for (int j = i; j < N; j++) {
                if (array[j] < min) {
                    array[i] = array[j];
                    array[j] = min;
                    min = array[i];
                }
            }
//            printArray(array);
        }
        long end = System.currentTimeMillis();
        long cost = end - start;
        System.out.println("use：" + cost + "s");
    }

    /**
     * 插入排序
     * 与前面的比较，在前面排好序的元素中找位置
     */
    public static void Insertion(int[] array) {
        Date start = new Date();
        System.out.println("插入排序");
        int N = array.length;
        for (int i = 0; i < N; i++) {
            for (int j = i; j > 0 && array[j] < array[j - 1]; j--) {
                int temp = array[j];
                array[j] = array[j - 1];
                array[j - 1] = temp;
            }
//            printArray(array);
        }
        Date end = new Date();
        long cost = end.getTime() - start.getTime();
        System.out.println("use：" + cost + "s");
    }

    /**
     * 希尔排序
     * 块状元素的插入排序
     */
    public static void Shell(int[] array) {
        Date start = new Date();
        System.out.println("希尔排序");
        int N = array.length;
        int d = 1;
        while (d < N / 3) d = 3 * d + 1;
        while (d > 0) {
            for (int i = d; i < N; i++) {
                for (int j = i; j - d >= 0 && array[j] < array[j - d]; j -= d) {
                    int temp = array[j];
                    array[j] = array[j - d];
                    array[j - d] = temp;
                }
//                printArray(array);
            }
            d = d / 3;
        }
        Date end = new Date();
        long cost = end.getTime() - start.getTime();
        System.out.println("use：" + cost + "s");
    }

    /**
     *
     *
     */
    public static void Merge(int[] array) {
        long start = System.currentTimeMillis();
        System.out.println("归并排序（自顶向下）");

        Merge.sort(array);

        long end = System.currentTimeMillis();
        long cost = end - start;
        System.out.println("use：" + cost + "s");
    }

    public static void MergeBU(int[] array) {
        long start = System.currentTimeMillis();
        System.out.println("归并排序（自底向上）");

        Merge.sortBU(array);

        long end = System.currentTimeMillis();
        long cost = end - start;
        System.out.println("use：" + cost + "s");
    }

    public static void Quick(int[] array) {
        long start = System.currentTimeMillis();
        System.out.println("快速排序");

        Quick.sort(array);

        long end = System.currentTimeMillis();
        long cost = end - start;
        System.out.println("use：" + cost + "s");
    }
}
